class Solution:
    def wordBreak(self, s: str, wordDict: list) -> list:
        def func(string, index, wordDict, maxLen, cache):
            if index >= len(string):
                return []
            if index in cache:
                return cache[index]
            res = []
            word = ""
            length = maxLen + index if len(string) > maxLen + index else len(
                string)
            for i in range(index, length):
                word += string[i]
                if word in wordDict:
                    nextWordSet = func(string, i + 1, wordDict, maxLen,
                                       cache)
                    if nextWordSet is None:
                        continue
                    if nextWordSet:
                        for wordSet in nextWordSet:
                            res.append(word + " " + wordSet)
                    else:
                        res.append(word)
            if len(res) == 0:
                cache[index] = None
            else:
                cache[index] = res

            return cache[index]

        maxLen = 0
        for word in wordDict:
            maxLen = max(maxLen, len(word))
        wordDict = set(wordDict)
        return func(s, 0, wordDict, maxLen, {})
